package com.gxc.tree;

/**
 * morris遍历--利用底层结点的大量空指针
 * 时间复杂度O(N)，额外空间复杂度O(1)
 * Morris遍历细节
 假设来到当前节点cur，开始时cur来到头节点位置
 1)如果cur没有左孩子，cur向右移动(cur = cur.right)
 2)如果cur有左孩子，找到左子树上最右的节点mostRight(mostRight!=cur--b情况程序人为改动过):
        a.如果mostRight的右指针指向空，让其指向cur，然后cur向左移动(cur = cur.left)
        b.如果mostRight的右指针指向cur，让其指向null.然后cur向右移动(cur = cur.right)
 3)cur为空时遍历停止
 */
public class Morris {

    public static void morris(TreeBean head) {
        if (head == null) return;

        TreeBean cur = head;
        TreeBean mostRight = null;
        while (cur != null) {
            mostRight = cur.left;
            if (mostRight == null) cur =cur.right;
            else {
                while (mostRight != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) {
                    mostRight.right = cur;
                    cur =cur.left;
                } else if (mostRight == cur) {
                    mostRight.right = null;
                    cur = cur.right;
                }
            }
        }
    }

    /**
     * morris 先序遍历
     * 只出现一次的节点直接打印
     * 出现两次的节点，第一次出现时，直接打印
     * @param head
     */
    private static void preorderMorris(TreeBean head) {
        if (head == null) return;

        TreeBean cur = head;
        TreeBean mostRight = null;
        while (cur != null) {
            mostRight = cur.left;
            if (mostRight == null) {
                System.out.println(cur.value);
                cur =cur.right;
            }
            else {
                while (mostRight != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) {
                    System.out.println(cur.value);
                    mostRight.right = cur;
                    cur =cur.left;
                } else if (mostRight == cur) {
                    mostRight.right = null;
                    cur = cur.right;
                }
            }
        }
    }

    /**
     * morris 中序遍历
     * 只出现一次的节点直接打印
     * 出现两次的节点，第二次出现时，打印
     * @param head
     */
    private static void inorderMorris(TreeBean head) {
        if (head == null) return;

        TreeBean cur = head;
        TreeBean mostRight = null;
        while (cur != null) {
            mostRight = cur.left;
            if (mostRight == null) {
                System.out.println(cur.value);
                cur = cur.right;
            } else {
                while (mostRight != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) {
                    mostRight.right = cur;
                    cur = cur.left;
                } else if (mostRight == cur) {
                    System.out.println(cur.value);
                    mostRight.right = null;
                    cur = cur.right;
                }
            }
        }
    }

    /**
     * 后续遍历
     * 出现两次的节点，第二次出现时，逆序打印左子树的右边界
     * 遍历完之后，打印整颗树的右边界
     * @param head
     */
    public static void afterOrder(TreeBean head){
        if (head == null) return;

        TreeBean cur = head;
        TreeBean mostRight = null;
        while (cur != null) {
            mostRight = cur.left;
            if (mostRight == null) cur =cur.right;
            else {
                while (mostRight != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) {
                    mostRight.right = cur;
                    cur =cur.left;
                } else if (mostRight == cur) {
                    //逆序打印树的右边界
                    printRight(cur.left);

                    mostRight.right = null;
                    cur = cur.right;
                }
            }
        }
        //打印整颗树的右边界
        printRight(head);
    }

    /**
     * 逆序打印树的右边界
     * @param node
     */
    public static void printRight(TreeBean node){
        TreeBean reverse = reverse(node);
        TreeBean cur = reverse;
        while (cur!=null) {
            System.out.println(cur.value + "  ");
            cur = cur.right;
        }
        reverse(reverse);
    }

    //逆序
    public static TreeBean reverse(TreeBean from) {
        TreeBean pre = null;
        TreeBean next = null;
        while (from != null) {
            next = from.right;
            from.right=pre;
            pre = from;
            from = next;
        }
        return pre;
    }

    /**
     * 是否搜索二叉树
     * 中序遍历是否有序
     * @param head
     */
    private static boolean isBST(TreeBean head) {
        if (head == null) return false;

        TreeBean cur = head;
        TreeBean mostRight = null;
        int max = Integer.MIN_VALUE;
        while (cur != null) {
            mostRight = cur.left;
            if (mostRight == null) {
                if (cur.value<=max) return false;
                max = cur.value;
                cur = cur.right;
            } else {
                while (mostRight != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) {
                    mostRight.right = cur;
                    cur = cur.left;
                } else if (mostRight == cur) {

                    if (cur.value<=max) return false;
                    max = cur.value;

                    mostRight.right = null;
                    cur = cur.right;
                }
            }
        }
        return true;
    }
}
